// https://www.lintcode.com/problem/palindrome-permutation-ii/my-submissions

class Solution {
public:
    /**
     * @param s: the given string
     * @return: all the palindromic permutations (without duplicates) of it
     */
     
    void getPalindromes(string &s, int begin, int end, vector<string>& result)
    {
        if (begin == end)
        {
            if (find(result.begin(), result.end(), s) == result.end())
                result.push_back(s);
        }
        for (int i = begin; i <= end; ++i)
        {
            if (i == begin || s[i] != s[begin]) // 注意去重，防止超时
            {
                swap(s[begin], s[i]);
                getPalindromes(s, begin + 1, end, result);
                swap(s[begin], s[i]);
            }
        }
    }
    
    vector<string> generatePalindromes(string &s) {
        map<char, int> record_map;
        vector<string> result;
        vector<string> tmp_results;
        string tmp_s = "";
        for (char c: s)
        {
            record_map[c]++;
        }
        map<char, int>::iterator it = record_map.begin();
        string oddString = "";
        while (it != record_map.end())
        {
            if ((it->second) % 2 == 1)
            {
                if (oddString != "") return result; 
                oddString = it->first;
                it->second--;
            }
            int n = (it->second) / 2;
            char c = it->first;
            while (n--)
            {
                tmp_s += c;
            }
            ++it;
        }
        getPalindromes(tmp_s, 0, tmp_s.length() - 1, tmp_results);
        for (string s: tmp_results)
        {
            string s_re = s;
            reverse(s_re.begin(), s_re.end());
            result.push_back(s + oddString + s_re);
        }
        return result;
    }
};

